package cn.zifangsky.graph;


import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.queue.Queue;

import java.text.MessageFormat;
import java.util.Arrays;
import java.util.List;
import java.util.function.Consumer;

/**
 * 邻接表
 *
 * @author zifangsky
 * @date 2019/1/18
 * @since 1.0.0
 */
public class GraphList {

    /**
     * 边节点信息
     */
    static class EdgeNode {
        /**
         * 起始顶点
         */
        private String startVertex;
        /**
         * 结束顶点
         */
        private String endVertex;
        /**
         * 边的权重（无向图的边的权重为1）
         */
        private Integer weight;
        /**
         * 起始顶点相邻的下一条边
         */
        EdgeNode next;

        public EdgeNode(String startVertex, String endVertex, Integer weight) {
            this.startVertex = startVertex;
            this.endVertex = endVertex;
            this.weight = weight;
            this.next = null;
        }

        public EdgeNode(String startVertex, String endVertex, Integer weight, EdgeNode next) {
            this.startVertex = startVertex;
            this.endVertex = endVertex;
            this.weight = weight;
            this.next = next;
        }

        public String getStartVertex() {
            return startVertex;
        }

        public String getEndVertex() {
            return endVertex;
        }

        public Integer getWeight() {
            return weight;
        }

        public EdgeNode getNext() {
            return next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "startVertex='" + startVertex + '\'' +
                    ", endVertex='" + endVertex + '\'' +
                    ", weight=" + weight +
                    ", next=" + next +
                    '}';
        }
    }

    /**
     * 顶点信息
     */
    static class VertexNode {
        /**
         * 顶点名
         */
        private String name;
        /**
         * 相邻的边节点
         */
        private EdgeNode edgeNode;

        public VertexNode(String name) {
            this.name = name;
            this.edgeNode = null;
        }

        public VertexNode(String name, EdgeNode edgeNode) {
            this.name = name;
            this.edgeNode = edgeNode;
        }

        public String getName() {
            return name;
        }

        public EdgeNode getEdgeNode() {
            return edgeNode;
        }

        /**
         * 检查邻接表上是否包含某个顶点
         * @param vertex 待检查的顶点
         * @return boolean
         */
        public boolean contains(String vertex){
            if(vertex != null){
                EdgeNode temp = edgeNode;
                while (temp != null){
                    if(vertex.equals(temp.endVertex)){
                        return true;
                    }

                    temp = temp.next;
                }
            }

            return false;
        }

        @Override
        public String toString() {
            return "VertexNode{" +
                    "name='" + name + '\'' +
                    ", edgeNode=" + edgeNode +
                    '}';
        }
    }

    /* ---------------- Fields -------------- */

    /**
     * 顶点个数
     */
    private int vertexNum;

    /**
     * 顶点数组
     */
    private List<String> vertexList;

    /**
     * 邻接表
     */
    private VertexNode[] list;

    /**
     * 是否是有向图（默认为无向图）
     */
    private boolean directedGraph = false;

    public int getVertexNum() {
        return vertexNum;
    }

    public List<String> getVertexList() {
        return vertexList;
    }

    public VertexNode[] getList() {
        return list;
    }

    public boolean isDirectedGraph() {
        return directedGraph;
    }

    /**
     * 构造方法
     * @author zifangsky
     * @date 2019/1/23 16:21
     * @since 1.0.0
     * @param vertexArray 顶点数组
     * @param weightList 顶点之间的权重
     */
    public GraphList(String[] vertexArray, List<Edge> weightList) {
        if (vertexArray == null || vertexArray.length < 1
                || weightList == null) {
            throw new IllegalArgumentException("Illegal initial initialArray");
        }

        this.vertexNum = vertexArray.length;
        this.vertexList = Arrays.asList(vertexArray);

        //初始化图
        this.initGraph(weightList, this.directedGraph);
    }

    /**
     * 构造方法
     * @author zifangsky
     * @date 2019/1/23 16:21
     * @since 1.0.0
     * @param vertexArray 顶点数组
     * @param weightList 顶点之间的权重
     * @param directedGraph 是否是有向图（默认为无向图）
     */
    public GraphList(String[] vertexArray, List<Edge> weightList, boolean directedGraph) {
        if (vertexArray == null || vertexArray.length < 1
                || weightList == null) {
            throw new IllegalArgumentException("Illegal initial initialArray");
        }

        this.vertexNum = vertexArray.length;
        this.vertexList = Arrays.asList(vertexArray);
        this.directedGraph = directedGraph;

        //初始化图
        this.initGraph(weightList, this.directedGraph);
    }

    /**
     * 初始化图
     * @param weightList 顶点之间的权重
     * @param directedGraph 是否是有向图（默认为无向图）
     */
    private void initGraph(List<Edge> weightList, boolean directedGraph){
        //1. 初始化邻接表
        list = new VertexNode[vertexNum];
        for(int i = 0; i < vertexNum; i++){
            list[i] = new VertexNode(vertexList.get(i));
        }

        //2. 根据边信息构建邻接表
        for(Edge edge : weightList){
            //将一条边信息插入到邻接表中
            this.insertGraphList(vertexList, edge);

            //如果是无向图，相反的边也插入
            if(!directedGraph){
                this.insertGraphList(vertexList, new Edge(edge.getEndVertex(), edge.getStartVertex(), edge.getWeight()));
            }
        }
    }

    /**
     * 将一条边插入到邻接表中
     */
    private void insertGraphList(List<String> vertexList, Edge edge){
        //1. 找到起始和结束索引
        int startIndex = vertexList.indexOf(edge.getStartVertex());
        int endIndex = vertexList.indexOf(edge.getEndVertex());

        if(startIndex < 0 || endIndex < 0){
            throw new RuntimeException(MessageFormat.format("初始化数据存在问题：{0}", edge));
        }

        //2. 构建邻接表
        EdgeNode newNode = new EdgeNode(edge.getStartVertex(), edge.getEndVertex(), edge.getWeight());
        //找到起始顶点在顶点数组中的位置
        VertexNode vertexNode = list[startIndex];

        //只有当邻接表上不存在待插入节点，才真正插入
        if(!vertexNode.contains(edge.getEndVertex())){
            //当前顶点的第一个邻接顶点
            EdgeNode root = vertexNode.edgeNode;
            //如果当前没有邻接顶点，则将新顶点挂上去，否则将新顶点挂到链表末尾
            if(root == null){
                vertexNode.edgeNode = newNode;
            }else{
                while (root.next != null){
                    root = root.next;
                }

                root.next = newNode;
            }
        }

    }

    /**
     * 遍历
     * @author zifangsky
     * @date 2019/1/23 16:27
     * @since 1.0.0
     * @param consumer consumer
     */
    public void foreach(Consumer<String> consumer){
        if(consumer != null){
            if(list != null){
                for(VertexNode vertexNode : list){
                    if(vertexNode != null){
                        StringBuffer stringBuffer = new StringBuffer(vertexNode.name);

                        EdgeNode root = vertexNode.edgeNode;
                        while (root != null){
                            stringBuffer.append(" --> " + root.endVertex);
                            root = root.next;
                        }

                        consumer.accept(stringBuffer.toString());
                    }

                }
            }
        }
    }

    /**
     * DFS（深度优先搜索）
     * @author zifangsky
     * @date 2019/1/23 17:50
     * @since 1.0.0
     * @param consumer consumer
     */
    public void dfsForeach(Consumer<String> consumer){
        //标识每个顶点是否被访问
        boolean[] visited = new boolean[vertexNum];
        for(int i = 0; i < vertexNum; i++){
            visited[i] = false;
        }

        for(int i = 0; i < vertexNum; i++){
            if(!visited[i]){
                this.dfs(visited, i, consumer);
            }
        }
    }

    /**
     * DFS（深度优先搜索）
     * @param visited 标识每个顶点是否被访问
     * @param vertexIndex 顶点索引
     * @param consumer consumer
     */
    private void dfs(boolean[] visited, int vertexIndex, Consumer<String> consumer){
        VertexNode current = list[vertexIndex];

        //1. 输出当前顶点，并将标识置为——已访问
        consumer.accept(current.name);
        visited[vertexIndex] = true;

        //2. 遍历当前顶点的相邻节点
        EdgeNode temp = current.edgeNode;
        while (temp != null){
            //相邻节点的索引
            int index = vertexList.indexOf(temp.endVertex);
            if(!visited[index]){
                this.dfs(visited, index, consumer);
            }
            temp = temp.next;
        }
    }

    /**
     * BFS（宽度优先搜索）
     * @author zifangsky
     * @date 2019/1/23 17:54
     * @since 1.0.0
     * @param consumer consumer
     */
    public void bfsForeach(Consumer<String> consumer){
        //定义一个队列
        Queue<String> queue = new LinkQueue<>();

        //标识每个顶点是否被访问
        boolean[] visited = new boolean[vertexNum];
        for(int i = 0; i < vertexNum; i++){
            visited[i] = false;
        }

        queue.push(vertexList.get(0));

        //1. 如果队列不为空，则一直遍历
        while (!queue.isEmpty()){
            //2. 出队，获取顶点
            String vertex = queue.pop();
            int vertexIndex = vertexList.indexOf(vertex);
            //当前遍历的顶点
            VertexNode current = list[vertexIndex];
            consumer.accept(vertex);

            //3. 标识改顶点已经被访问
            visited[vertexIndex] = true;

            //4. 遍历当前顶点的相邻节点
            EdgeNode temp = current.edgeNode;
            while (temp != null){
                //相邻节点的索引
                int index = vertexList.indexOf(temp.endVertex);
                if(!visited[index]){
                    queue.pushIfNotExist(vertexList.get(index));
                }
                temp = temp.next;
            }
        }
    }
}
